#pragma once
#include <vector>
#include <algorithm>
using namespace std;

//最长上升子序列（Longest Increasing Subsequence，LIS）
//我们要求序列中最长的单调增的 子序列（不一定连续）的长度
//注意：这里是指 子序列 而非 子串


/*
* 解法一 ：动态规划
* 另 d(i) 表示为最长子序列的长度
* d(i) 就是找以A[i]结尾的，在A[i]之前的最长上升子序列 +1
* 即前 i 个数的 LIS 长度 + 1。当A[i]之前没有比A[i]更小的数时，d(i) = 1
*/

/*
* 每次都向前找比它小的数和比它大的数的位置，将第一个比它大的替换掉
* 这样操作虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的
*/

int LISByDP(const vector<int>& sequence)
{
	vector<int> LISsize(sequence.size(), 1);

	for (int i = 0; i < sequence.size(); i++) {
		for (int j = 0; j < i; j++) {
			if (sequence[j] <= sequence[i]) {
				LISsize[i] = max(LISsize[i], LISsize[j] + 1);
			}
		}
	}
	return *max_element(LISsize.begin(), LISsize.end());
}